/**
 * 红黑树
 */
;(function(window){
	var Node = function(data){
		return {
			data: data,
			color: 'B',
			parent: null,
			rChild: null,
			lChild: null
		};
	};

	var RedBlackTree = function(){
		this._nil = Node(null);
		this._root = this._nil;
	};
	RedBlackTree.prototype = {
		constructor: RedBlackTree,
		/**
		 * 左旋转
		 * @param node
		 * @private
		 */
		_rotateLeft: function(node){
			var yNode;
			yNode = node.rChild;
			node.rChild = yNode.lChild;
			if(yNode.lChild != this._nil ){
				yNode.lChild.parent = node;
			}
			yNode.parent = node.parent;
			if(node.parent == this._nil){
				this._root = yNode;
			}
			else if(node == node.parent.lChild){
				node.parent.lChild = yNode;
			}
			else{
				node.parent.rChild = yNode;
			}
			yNode.lChild = node;
			node.parent = yNode;
		},
		/**
		 * 右旋转
		 * @param node
		 * @private
		 */
		_rotateRight: function(node){
			var yNode;
			yNode = node.lChild;
			node.lChild = yNode.rChild;
			if(yNode.rChild != this._nil){
				yNode.rChild.parent = node;
			}
			yNode.parent = node.parent;
			if(node.parent == this._nil){
				this._root =yNode;
			}
			else if(node == node.parent.lChild){
				node.parent.lChild = yNode;
			}
			else{
				node.parent.rChild = yNode;
			}
			yNode.rChild = node;
			node.parent = yNode;
		},
		/**
		 * 插入后修复红黑树
		 * @param node
		 * @private
		 */
		_insertFixUp: function(node){
			var yNode = this._nil;
			while(node.parent.color =='R'){
				if(node.parent == node.parent.parent.lChild){
					yNode = node.parent.parent.rChild;
					if(yNode.color == 'R'){
						node.parent.color ="B";
						yNode.color = "B";
						node.parent.parent.color ="R";
						node = node.parent.parent;
					}else{
						if(node == node.parent.rChild){
							node = node.parent;
							this._rotateLeft(node);
						}
						node.parent.color = "B";
						node.parent.parent.color = "R";
						this._rotateRight(node.parent.parent);
					}
				}else{
					yNode = node.parent.parent.lChild;
					if(yNode.color == "R"){
						node.parent.color ="B";
						yNode.color = "B";
						node.parent.parent.color ="R";
						node = node.parent.parent;
					}
					else{
						if(node == node.parent.lChild){
							node = node.parent;
							this._rotateRight(node);
						}
						node.parent.color = "B";
						node.parent.parent.color = "R";
						this._rotateLeft(node.parent.parent);
					}
				}
			}
			this._root.color = "B";
		},
		/**
		 * 删除后修复红黑树
		 * @param xNode
		 * @private
		 */
		_deleteFixUp: function(xNode){
			var w;
			while(xNode!=this._root && xNode.color =="B"){
				if(xNode == xNode.parent.lChild){
					w = xNode.parent.rChild;
					if(w.color =="R"){
						w.color = "B";
						w.parent.color ="R";
						this._rotateLeft(xNode.parent);
						w = xNode.parent.rChild;
					}
					if(w.lChild.color == "B" && w.rChild.color == "B"){
						w.color ="R";
						xNode= xNode.parent;
					}
					else{
						if(w.rChild.color =="B"){
							w.lChild.color ="R";
							w.color = "B";
							this._rotateRight(xNode);
							w=xNode.parent.rChild;
						}
						w.color = xNode.parent.color;
						xNode.parent.color = "B";
						w.rChild.color ="B";
						this._rotateLeft(xNode.parent);
						xNode = this._root;
					}
				}
				else{
					w = xNode.parent.lChild;
					if(w.color =="R"){
						w.color = "B";
						w.parent.color ="R";
						this._rotateLeft(xNode.parent);
						w = xNode.parent.rChild;
					}
					if(w.lChild.color == "B" && w.rChild.color == "B"){
						w.color ="R";
						xNode= xNode.parent;
					}
					else{
						if(w.rChild.color =="B"){
							w.lChild.color ="R";
							w.color = "B";
							this._rotateLeft(t,xNode);
							w=xNode.parent.rChild;
						}
						w.color = xNode.parent.color;
						xNode.parent.color = "B";
						w.rChild.color ="B";
						this._rotateRight(xNode.parent);
						xNode = this._root;
					}
				}
			}
			xNode.color = "B";
		},
		/**
		 * 从某个节点开始向下查找最小值
		 * @param node
		 * @return {Node}
		 * @private
		 */
		_getMinimum: function(node){
			while(node.lChild != this._nil)
				node = node.lChild;
			return node;
		},
		/**
		 * 从某个节点开始向下查找最大值
		 * @param node
		 * @return {Node}
		 * @private
		 */
		_getMaximum: function(node){
			while(node.rChild != this._nil)
				node = node.rChild;
			return node;
		},
		/**
		 * 将v节点移植到u节点的位置
		 * @param u
		 * @param v
		 * @private
		 */
		_transplant: function(u,v){
			if(u.parent == this._nil )
				this._root = v;
			else if( u == u.parent.lChild )
				u.parent.lChild = v;
			else u.parent.rChild = v;
			v.parent = u.parent;
		},
		/**
		 * 插入数据
		 * @param data
		 */
		insert: function(data){
			var xNode = this._root,
				pNode = this._nil;
			var node = Node(data);
			while(xNode != this._nil){
				pNode = xNode;
				if( node.data < xNode.data) xNode = xNode.lChild;
				else xNode = xNode.rChild;
			}
			node.parent = pNode;
			if( pNode == this._nil ){
				this._root = node;
			}else if( node.data< pNode.data){
				pNode.lChild = node;
			}else{
				pNode.rChild = node;
			}
			node.color = 'R';
			node.lChild = this._nil;
			node.rChild = this._nil;
			this._insertFixUp(node);
		},
		/**
		 * 删除数据
		 * @param key
		 * @return {*}
		 */
		deleteNode: function(key){
			var z = this.getNode(key);
			var y = z,
				oColor = y.color,
				x;
			if(z.lChild == this._nil ){
				x = z.rChild;
				this._transplant(z, z.rChild);
			}else if(z.rChild == this._nil ){
				x = z.lChild;
				this._transplant(z, z.lChild);
			}else{
				y = this._getMinimum(z.rChild);
				oColor = y.color;
				x = y.rChild;
				if(y.parent == z){
					x.parent = y;
				}else{
					this._transplant(y, y.rChild);
					y.rChild = z.rChild;
					y.rChild.parent = y;
				}
				this._transplant(z, y);
				y.lChild = z.lChild;
				y.lChild.parent = y;
				y.color = z.color;
			}
			if( oColor == 'B' ) this._deleteFixUp(x);
			this._nil.parent = null;
			this._nil.color = 'B';
			return z;
		},
		/**
		 * 按给定的Key获取节点
		 * @param key
		 * @return {Node}
		 */
		getNode: function(key){
			if( this._root == this._nil ) return null;
			var node = this._root;
			while( node.data != key ){
				if( key > node.data ) node = node.rChild;
				if( key < node.data ) node = node.lChild;
				if( node == this._nil ) return null;
			}
			return node;
		},
		/**
		 * 获取整棵树的最小值
		 * @return {Node}
		 */
		getMinimum: function(){
			return this._getMinimum(this._root);
		},
		/**
		 * 获取整棵树的最大值
		 * @return {Node}
		 */
		getMaximum: function(){
			return this._getMaximum(this._root);
		},
		// 遍历
		/**
		 * 内部遍历方法
		 * @param node
		 * @param callback
		 * @param result
		 * @param type
		 * @return {Array}
		 * @private
		 */
		_traversal: function(node, callback, result, type){
			if( node != this._nil ){
				if( type == 'preOrder' ){
					callback(node);
					result.push(node.data);
				}
				this._traversal(node.lChild, callback, result, type);
				if( type == 'inOrder' ) {
					callback(node);
					result.push(node.data);
				}
				this._traversal(node.rChild, callback, result, type);
				if( type == 'postOrder' ) {
					callback(node);
					result.push(node.data);
				}
			}
			return result;
		},
		/**
		 * 中序遍历
		 * @param callback
		 * @return {Array}
		 */
		inOrderTraversal: function(callback){
			return this._traversal(this._root, callback, [], 'inOrder');
		},
		/**
		 * 前序遍历
		 * @return {Array}
		 */
		preOrderTraversal: function(callback){
			return this._traversal(this._root, callback, [], 'preOrder');
		},
		/**
		 * 后续遍历
		 * @return {Array}
		 */
		postOrderTraversal: function(callback){
			return this._traversal(this._root, callback, [], 'postOrder');
		}
	};

	window.RedBlackTree = RedBlackTree;
})(window);